/*
--------------------------------------------------------------------------------
				Ak-Lib. 
			 Project       	: Ak-Lib
			 Group         	: Ak-Lib R&D Team
			 Author        	: Ocean.Wang
			 Create Date 	: 05-01-2010
--------------------------------------------------------------------------------
Code Name 	:  A.K 	~v~
Description	:  Yet Another Cross-Platform Lib.
Cautions    	:
--------------------------------------------------------------------------------
Change History:
Version		: 0.1
Building 		: 05/01/10
10-05.01 first draft, build, debug and test.
--------------------------------------------------------------------------------
*/

#include "ak_clk.h"
#include "ak_lru.h"

/* ------------------------------------------------------------------
**	LTree (for LRU's GC Pri-Exp Node)
** User should Make sure Node1 & Node 2 Avail 
*/
#define SLRU_TICK_MAX 		((LONG_MAX-1)/2)
#define SLRU_TICK_JR 		(SLRU_TICK_MAX/2)
		
#define SLRU_TICK_RES 		_FREQ_MS_SCLK
#define SLRU_TICK_LAZY		8	
	
	/* We Use the Precision & Resolution to Reduce the LTree */
#define SLRU_TICK_REDU		4
#define SLRU_TICK_PREC		(SLRU_TICK_RES * SLRU_TICK_REDU)
	
#define SLRU_EXPIRE_LO(vExpire)  		 ((((vExpire)+ SLRU_TICK_PREC)/SLRU_TICK_PREC) * SLRU_TICK_REDU)
#define SLRU_EXPIRE_HI(vExpire)  		 (((vExpire) + SLRU_TICK_RES)/SLRU_TICK_RES)
	
#define SLRU_CALC_EXPIRE(vExpire, vCurrent) ((vExpire + (vCurrent))% SLRU_TICK_MAX)
	
	/* Item Type: GC - LRU */
#define SLRU_NUL 			0X00000000	/* Not needing GC */
#define SLRU_PRI			0X00000100	/* It's a Pri-Exp */
#define SLRU_SUB			0X00000200	/* It's a Sub-Exp */
#define SLRU_MASK 			0X00000F00

time_t 	SLru_TickStep(time_t current)
{
	current = (current + 1)%SLRU_TICK_MAX;
	return current;
}

static	int 	_LruTreeL_Cmp(_t_rbnode * node1, _t_rbnode * node2)
{
	time_t	expire1;
	time_t	expire2;
	
	expire1 = (_O_PARENT(_t_sysTi, lNode, node1))->expire;
	expire2 = (_O_PARENT(_t_sysTi, lNode, node2))->expire;

	if(expire1 > expire2){
		if((expire1 - expire2) < SLRU_TICK_JR)
			return _TREE_GREAT;
		else
			return _TREE_LESS;
	}
	else if(expire1 < expire2){
		if((expire2 - expire1) < SLRU_TICK_JR)
			return _TREE_LESS;
		else
			return _TREE_GREAT;
	}
	
	return _TREE_EQUAL;
}

static __inline	_t_sysLruCi * 	_LruTreeL_Find(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_rbnode 		*tNode;

	tNode = rb_find(&(pCt->lTree), &(pCi->ti.lNode), _LruTreeL_Cmp);
	if(tNode){
		return(_O_PARENT(_t_sysLruCi, ti.lNode, tNode));
	}
	return NULL;
}

int 	LruTreeL_Del(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_rbroot 		* tRoot;
	_t_sysLruCi	* pTemp;
	_t_snode  		* pNode;
	_t_snode  		* pNext;
	
	int 			type;

	type = (pCi->ti.type & SLRU_MASK);
	switch(type){
		case SLRU_NUL:
			/* Do Nothing */
			return 0;
			break;

		case SLRU_PRI:
			tRoot = &(pCt->lTree);

			pCi->ti.type &= ~SLRU_MASK;
			/* Judge Que's Count */
			pNode = &(pCi->ti.sNode);
			if(SNODE_ISOLATE(pNode)){
				rb_erase(tRoot, &(pCi->ti.lNode));
			}
			else{
				pNext = pNode->next;
				SNODE_DEL(pNode);
				pTemp = _O_PARENT(_t_sysLruCi, ti.sNode, pNext);
				/* Replace the Tree Node */
				rb_replace(tRoot, &(pCi->ti.lNode), &(pTemp->ti.lNode));

				/* Flush the Type */
				pTemp->ti.type &= ~SLRU_MASK;
				pTemp->ti.type |= SLRU_PRI; 
			}
			break;
			
		case SLRU_SUB:
			pNode = &(pCi->ti.sNode);
			SNODE_DEL(pNode);
			pCi->ti.type &= ~SLRU_MASK;
			break;

		default:
			/* Exception */
			break;
	}

	return -1;
}


void 		LruTreeL_Add(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_snode  	* pHead;
	_t_sysLruCi	* pTemp;

	pTemp = _LruTreeL_Find(pCt, pCi);	
	if(pTemp){
		pCi->ti.type &= ~SLRU_MASK;
		pCi->ti.type |= SLRU_SUB;

		pHead = &(pTemp->ti.sNode);
		SNODE_ADD2T(pHead, &(pCi->ti.sNode));
	}
	else{
		rb_insert(&(pCt->lTree), &(pCi->ti.lNode), _LruTreeL_Cmp);	
		pCi->ti.type &= ~SLRU_MASK;
		pCi->ti.type |= SLRU_PRI;

		pHead = &(pCi->ti.sNode);
		SNODE_INIT(pHead);
	}

	return ;
}


_t_sysLruCi * 	LruTreeK_Add(_t_sysLruCt * pCt, _t_sysLruCi * pCi, int (*fComp)())
{
	_t_rbroot 		* tRoot;
	_t_rbnode 		* tNode;
	_t_sysLruCi		* pTemp;
	pTemp = NULL;

	if(fComp){
		tRoot = &(pCt->kTree);

		tNode = rb_insert(tRoot, &(pCi->mi.kNode), fComp);	
		if(tNode){
			rb_replace(tRoot, tNode, &(pCi->mi.kNode));		
			pTemp = _O_PARENT(_t_sysLruCi, mi.kNode, tNode);
		}
	}
	return pTemp;
}

_t_sysLruCi * 	LruTreeK_Del(_t_sysLruCt * pCt, _t_sysLruCi * pCi, int (*fComp)())
{
	_t_sysLruCi * pTemp;
	pTemp = NULL;

	if(fComp){
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, fComp);
		if(pTemp){
			LruTreeK_Rm(pCt, pTemp);
		}
	}

	return pTemp;
}

_t_sysLruCi * 	LruTreeK_Get(_t_sysLruCt * pCt, _t_sysLruCi * pCi, int (*fComp)())
{
	_t_sysLruCi * pTemp;
	pTemp = NULL;

	if(fComp){
		SYS_LOCK_RD_TAKE(&(pCt->lock));
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, fComp);
		SYS_LOCK_RW_GIVE(&(pCt->lock));
	}

	return pTemp;
}


int 	SLru_Expire(_t_sysLruCt * pLruCt, time_t expire, long  lazyCnt)
{
	_t_snode  * 	pNode;
	_t_snode  * 	pNext;

	_t_sysLruCi*	pPriExp;
	_t_sysLruCi*	pSubExp;
	_t_sysKLFunc   * 	pHC;
	_t_sysLruCi		nExp;

	_t_blist 		recycle;
	
	long 			flag, diff;
	
	/* Fake the Expire Node */
	flag = 0;
	if(pLruCt && (pHC = pLruCt->klFunc)){
		diff = (expire + SLRU_TICK_MAX - pLruCt->lazy)%SLRU_TICK_MAX;
		if(diff > lazyCnt){
			diff = lazyCnt;
			flag = -1;
		}

		BLIST_INIT(&recycle);
		nExp.ti.expire 	= pLruCt->lazy;
		pLruCt->lazy 	= (pLruCt->lazy + diff)%SLRU_TICK_MAX;

		while(diff--){
			/* Search the Pri-Exp Node */
			SYS_LOCK_WR_TAKE(&(pLruCt->lock));
			
			pPriExp = _LruTreeL_Find(pLruCt, &nExp);
			if(pPriExp){
				/* Expire Que, Sub-Exp Node */
				pNode = &(pPriExp->ti.sNode);
				pNext = pNode->next;
				while(pNext != pNode){
					pSubExp = _O_PARENT(_t_sysLruCi, ti.sNode, pNext);
					pNext = pNext->next;

					/* Key-Value  & Recycle */
					pSubExp->ti.type &= ~SLRU_MASK;
					LruTreeK_Del(pLruCt, pSubExp, pHC->keyComp);
					BLST_ADD2T(&recycle, &(pSubExp->mi.aNode));
				}

				/* LRU & Key-Value  & Recycle */
				pPriExp->ti.type &= ~SLRU_MASK;
				rb_erase(&(pLruCt->lTree), &(pPriExp->ti.lNode));
				LruTreeK_Del(pLruCt, pPriExp, pHC->keyComp);
				BLST_ADD2T(&recycle, &(pPriExp->mi.aNode));
				
			}
			SYS_LOCK_RW_GIVE(&(pLruCt->lock));
			
			nExp.ti.expire = (nExp.ti.expire + 1)%SLRU_TICK_MAX;
		}

		/* Here We Free the Mi */
		pLruCt->stat_Expire += recycle.count;
		if(pHC->fExpireQ){
			pHC->fExpireQ(pLruCt, &recycle);
		}
	}
	
	return flag;
}

_t_sysLruCi * 	SLru_Del(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_sysLruCi * pTemp;
	_t_sysKLFunc 	* pHC;
	pTemp = NULL;

	if(pCt && pCi && (pHC = pCt->klFunc)){
		SYS_LOCK_WR_TAKE(&(pCt->lock));
		
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, pHC->keyComp);
		if(pTemp){
			LruTreeL_Del(pCt, pTemp);
			LruTreeK_Del(pCt, pTemp, pHC->keyComp);
		}
		
		SYS_LOCK_RW_GIVE(&(pCt->lock));
	}

	return pTemp;
}

_t_sysLruCi * 	SLru_DelEx(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_sysLruCi * pTemp;
	_t_sysKLFunc 	* pHC;
	pTemp = NULL;

	if(pCt && pCi && (pHC = pCt->klFunc)){
		SYS_LOCK_WR_TAKE(&(pCt->lock));
		
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, pHC->keyComp);
		if(pTemp && (pTemp == pCi)){
			LruTreeL_Del(pCt, pTemp);
			LruTreeK_Del(pCt, pTemp, pHC->keyComp);
		}else{
			pTemp = NULL;
		}
		
		SYS_LOCK_RW_GIVE(&(pCt->lock));
	}

	return pTemp;
}

int 	SLru_Rm(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_sysLruCi * pTemp;
	_t_sysKLFunc 	* pHC;
	pTemp = NULL;

	if(pCt && pCi && (pHC = pCt->klFunc)){
		SYS_LOCK_WR_TAKE(&(pCt->lock));
		
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, pHC->keyComp);
		if(pTemp){
			LruTreeL_Del(pCt, pTemp);
			LruTreeK_Del(pCt, pTemp, pHC->keyComp);
		}
		
		SYS_LOCK_RW_GIVE(&(pCt->lock));
		
		if(pTemp && (pHC->fFree)){
			pHC->fFree(pCt, pTemp);
		}
	}


	return 0;
}


int 	SLru_RmEx(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_sysLruCi * pTemp;
	_t_sysKLFunc 	* pHC;
	pTemp = NULL;

	if(pCt && pCi && (pHC = pCt->klFunc)){
		SYS_LOCK_WR_TAKE(&(pCt->lock));
		
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, pHC->keyComp);
		if(pTemp && (pTemp == pCi)){
			LruTreeL_Del(pCt, pTemp);
			LruTreeK_Del(pCt, pTemp, pHC->keyComp);
		}else{
			pTemp = NULL;
		}
		
		SYS_LOCK_RW_GIVE(&(pCt->lock));
		
		if(pTemp && (pHC->fFree)){
			pHC->fFree(pCt, pTemp);
		}
	}


	return 0;
}

_t_sysLruCi * 	SLru_Get(_t_sysLruCt * pCt, _t_sysLruCi * pCi, void * pData, size_t lData)
{
	_t_sysLruCi * pTemp;
	_t_sysKLFunc 	* pHC;
	pTemp = NULL;

	if(pCt && pCi && (pHC = pCt->klFunc)){
		SYS_LOCK_RD_TAKE(&(pCt->lock));
		
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, pHC->keyComp);
		if(pTemp && pHC->fDataGet){
			pHC->fDataGet(pTemp, pData, lData);
		}

		SYS_LOCK_RW_GIVE(&(pCt->lock));
	}

	return pTemp;
}

static 	__inline 	void 	_SLru_AddL(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	/* LRU */
	if(pCi->ti.expire > 0){
		pCi->ti.expire = SLRU_CALC_EXPIRE(SLRU_EXPIRE_HI(pCi->ti.expire),  *(pCt->current));
		LruTreeL_Add(pCt, pCi);
	}else{
		pCi->ti.type &= ~SLRU_MASK;
	}
	return;
}

int 	SLru_Add(_t_sysLruCt * pCt, _t_sysLruCi * pCi)
{
	_t_sysLruCi * pTemp;
	_t_sysKLFunc 	* pHC;
	
	pTemp = NULL;
	
	if(pCt && pCi && (pHC = pCt->klFunc)){
		SYS_LOCK_WR_TAKE(&(pCt->lock));
		
		/* Key-Value */
		pTemp = (_t_sysLruCi *)LruTreeK_Add(pCt, pCi, pHC->keyComp);
		if(pTemp){
			LruTreeL_Del(pCt, pTemp);
		}
		/* LRU */
		_SLru_AddL(pCt, pCi);
		#if 0
		if(pCi->ti.expire > 0){
			pCi->ti.expire = SLRU_CALC_EXPIRE(SLRU_EXPIRE_HI(pCi->ti.expire),  *(pCt->current));
			LruTreeL_Add(pCt, pCi);
		}else{
			pCi->ti.type &= ~SLRU_MASK;
		}
		#endif
		
		SYS_LOCK_RW_GIVE(&(pCt->lock));

		if(pTemp && (pHC->fFree)){
			pHC->fFree(pCt, pTemp);
		}
	}


	return 0;
}

_t_sysLruCi * 	SLru_Replace(_t_sysLruCt * pCt, _t_sysLruCi * pCi, _t_sysLruCi ** ppClea, void * pData, size_t lData)
{
	_t_sysLruCi * pRepl;
	_t_sysLruCi * pClea;
	_t_sysKLFunc 	* pHC;

	pRepl 	= NULL;
	pClea 	= NULL;
	*ppClea	= NULL;
	if(pCt && pCi && (pHC = pCt->klFunc) && ppClea){
		SYS_LOCK_WR_TAKE(&(pCt->lock));
		pRepl = (_t_sysLruCi *)rb_insert(&(pCt->kTree), &(pCi->mi.kNode), pHC->keyComp);
		if(pRepl){
			LruTreeL_Del(pCt, pRepl);

			/* Fill */
			if(pHC->fDataSet && pData){
				if(pRepl->mi.alkSize >= pCi->mi.alkSize){
					pHC->fDataSet(pRepl, pData, lData);
					
					/* Seting the Expire */
					pRepl->ti.expire = pCi->ti.expire;
					/* Switch */
					pClea 	= pCi;
					pCi 	= pRepl;
				}else{
					pHC->fDataSet(pCi, pData, lData);

					/* Replace */
					rb_replace(&(pCt->kTree), &(pRepl->mi.kNode), &(pCi->mi.kNode));	
					pClea = pRepl;
				}
			}
			else{
				/* Replace */
				rb_replace(&(pCt->kTree), &(pRepl->mi.kNode), &(pCi->mi.kNode));	
				pClea = pRepl;
			}
			
			/* LRU */
			_SLru_AddL(pCt, pCi);
			#if 0
			if(pCi->ti.expire > 0){
				pCi->ti.expire = SLRU_CALC_EXPIRE(SLRU_EXPIRE_HI(pCi->ti.expire),  *(pCt->current));
				LruTreeL_Add(pCt, pCi);
			}else{
				pCi->ti.type &= ~SLRU_MASK;
			}
			#endif
			
		}
		else{
			/* Fill */
			if(pHC->fDataSet && pData){
				pHC->fDataSet(pCi, pData, lData);
			}

			/* LRU */
			_SLru_AddL(pCt, pCi);
			#if 0
			if(pCi->ti.expire > 0){
				pCi->ti.expire = SLRU_CALC_EXPIRE(SLRU_EXPIRE_HI(pCi->ti.expire),  *(pCt->current));
				LruTreeL_Add(pCt, pCi);
			}
			else{
				pCi->ti.type &= ~SLRU_MASK;
			}
			#endif
		}
		SYS_LOCK_RW_GIVE(&(pCt->lock));

		/* Let's Free the Replaced Ci */
		*ppClea = pClea;
		if(pClea && pHC->fFree){
			pHC->fFree(pCt, pClea);
		}

	}

	
	return pCi;
}


_t_sysLruCi * 	SLru_SetExpire(_t_sysLruCt * pCt, _t_sysLruCi * pCi, unsigned int expire, _t_cbentry * pJudge)
{
	_t_sysLruCi * pTemp;
	_t_sysKLFunc 	* pHC;
	pTemp = NULL;

	if(pCt && pCi && (pHC = pCt->klFunc)){
		SYS_LOCK_WR_TAKE(&(pCt->lock));
		
		/* Key-Value */
		pTemp = _LruTreeK_Find(pCt, pCi, pHC->keyComp);
		if(pTemp == pCi){
			/* Check if Need Futher Judge  */
			if(pJudge){
				if(pJudge->cbProc(pJudge->pArg, pJudge->lArg, pCi) == 0){
					LruTreeL_Del(pCt, pCi);
					pCi->ti.expire = expire;
					/* LRU */
					_SLru_AddL(pCt, pCi);
					#if 0
					if(pCi->ti.expire > 0){
						pCi->ti.expire = SLRU_CALC_EXPIRE(SLRU_EXPIRE_HI(pCi->ti.expire),  *(pCt->current));
						LruTreeL_Add(pCt, pCi);
					}
					else{
						pCi->ti.type &= ~SLRU_MASK;
					}
					#endif
				}else{
					pTemp = NULL;
				}
			}
			else{
				LruTreeL_Del(pCt, pCi);
				pCi->ti.expire = expire;
				/* LRU */
				_SLru_AddL(pCt, pCi);
			}
			
		}
		else{
			pTemp = NULL;
		}

		SYS_LOCK_RW_GIVE(&(pCt->lock));
	}

	return pTemp;
}

